package mo.offer_special;

import mo.common.TreeNode;

public class L049 {

    public int sumNumbers(TreeNode root) {
        return dfs(new StringBuilder(), root);
    }

    private int dfs(StringBuilder builder, TreeNode node) {
        int sum = 0;
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            builder.append(node.val);
            sum += Integer.parseInt(builder.toString());
            builder.deleteCharAt(builder.length()-1);
            return sum;
        }
        builder.append(node.val);
        sum += dfs(builder, node.left);
        sum += dfs(builder, node.right);
        builder.deleteCharAt(builder.length()-1);
        return sum;
    }

    public static void main(String[] args) {
        L049 test = new L049();
        TreeNode root = new TreeNode(4);
        TreeNode left = new TreeNode(9);
        root.left = left;
        root.right = new TreeNode(0);
        left.left = new TreeNode(5);
        left.right = new TreeNode(1);
        System.out.println(test.sumNumbers(root));
    }

}
